The present invention relates to methods and apparatus for providing a cipher block chaining algorithm that produces a message authentication code, which may be executed on, for example, a pipelined processing system.
In recent years, there has been an insatiable desire for faster computer processing data throughputs because cutting-edge computer applications are becoming more and more complex, and are placing ever increasing demands on processing systems. Graphics applications are among those that place the highest demands on a processing system because they require such vast numbers of data accesses, data computations, and data manipulations in relatively short periods of time to achieve desirable visual results. Real-time, multimedia applications also place a high demand on processing systems; indeed, they require extremely fast processing speeds, such as many thousands of megabits of data per second.
While some processing systems employ a single processor to achieve fast processing speeds, others are implemented utilizing multi-processor architectures. In multi-processor systems, a plurality of sub-processors can operate in parallel (or at least in concert) to achieve desired processing results. These parallel processing systems may be adapted to form pipeline processors that perform repetitive processing algorithms in parallel. This is often useful in hiding algorithm and instruction latencies.
While pipeline processing is a desirable configuration, it is not always possible to efficiently process data through a pipeline. For example, a cipher block chaining algorithm that produces a message authentication code cannot be efficiently executed on a pipelined system. This is so because the processing stages in the chain depend on the data produced by previous stages and, therefore, the stages cannot be easily executed by separate pipelines.
For Example, with reference to FIG. 1, a cipher block chaining algorithm that produces a message authentication code (MAC) is illustrated in which a plurality of blocks of data, Bi, may be encoded to produce a message authentication code (MAC). In a first stage of the cipher block chaining algorithm, a first block of data B1 is subjected to a cipher function f(Bi) to produce a first cipher block C1. In the next stage of the cipher block chaining algorithm, a second block of data B2 is subjected to another cipher function f(Bi, Ci−1) to produce a second cipher block C2. It is noted that the cipher function of the second stage receives two inputs, namely, the second block of data B2 and the cipher block C1 of the previous stage. Thus, the second cipher block C2 is a function of the cipher block C1 of the previous stage. Subsequent stages of the cipher block chaining algorithm are substantially similar to the second stage, where the last stage of the cipher block chaining algorithm produces the MAC.
With reference to FIG. 2, each of the cipher blocks Ci is dependant upon on a corresponding block of data Bi and (with the exception of the first cipher block) a previous cipher block. Thus, any change to the blocks of data Bi will change the MAC. This provides a mechanism for authenticating the blocks of data Bi. Indeed, the MAC acts as a cryptographic checksum (or hash result) that is assigned to the data and used to test the data at a later date to verify that the data has not been maliciously changed. Without knowing the cipher block chaining algorithm that was used to create the MAC, it is highly unlikely that an unauthorized person would be able to change the data Bi without inadvertently changing the MAC. Thus, the MAC has value in the transmission of the data and/or storage of the data to insure that malicious tampering does not go undetected.
Unfortunately, the cipher block chaining algorithm described hereinabove is not suitable for pipeline processing because each stage of the algorithm depends on the cipher block produced in the previous stage. Accordingly, the stages may not be readily assigned to respective pipelines and executed in parallel. Consequently, the algorithm latency and instruction latency (associated with the given processor(s) executing the cipher block chaining algorithm) may not be hidden. Further, the authentication of the data Bi utilizing the MAC may become a significant bottleneck in a later-performed process.
Accordingly, there are needs in the art for new methods and apparatus for providing a cipher block chaining algorithm that produces a message authentication code, which may be executed on, for example, a pipelined processing system.